package previous.Test_0320;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //课程表
    public boolean canFinish(int n, int[][] p) {
          //度
         int[] du=new int[n];
        Map<Integer,List<Integer>> hash=new HashMap<>();
        //建图
        for (int i = 0; i < p.length; i++) {
            int a=p[i][0];
            int b=p[i][1];
            if(!hash.containsKey(b)) {
                hash.put(b,new ArrayList<>());
            }
            hash.get(b).add(a);
            du[a]++;
        }
        //拓扑排序
        Queue<Integer> q=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(du[i]==0) q.add(i);
        }
        //bfs
        while(!q.isEmpty()){
            int t=q.poll();
            for (int a:hash.getOrDefault(t,new ArrayList<>())) {
                du[a]--;
                if(du[a]==0) q.add(a);
            }
        }
        for (int x:du) {
            if(x!=0) return false;
        }
        return true;
    }
    //课程表2
    public int[] findOrder(int n, int[][] p) {
          //度
        int[] in=new int[n];
        //建图
        Map<Integer,List<Integer>> hash=new HashMap<>();
        for (int i = 0; i <p.length ; i++) {
            int a=p[i][0];
            int b=p[i][1];
            if(!hash.containsKey(b)){
                hash.put(b,new ArrayList<>());
            }
            hash.get(b).add(a);
            in[a]++;
        }
        int[] s=new int[n];
        int i=0;
        //拓扑排序
        Queue<Integer> q=new LinkedList<>();
        for (int j = 0; j < n; j++) {
            if(in[j]==0){
                q.add(j);
            }
        }
        while(!q.isEmpty()){
            int t=q.poll();
            s[i++]=t;
            for (int a:hash.getOrDefault(t,new ArrayList<>())) {
                in[a]--;
                if(in[a]==0){
                    q.add(a);

                }
            }
        }
        if(s.length==n) return s;
        else return new int[]{};
        //判断环
//        for (int j = 0; j < n; j++) {
//            if(in[j]!=0) {
//                return new int[]{};
//            }
//        }
    }
}
